{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Candy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: candy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分发糖果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 个孩子站成一排。给你一个整数数组 <code>ratings</code> 表示每个孩子的评分。</p>\n",
    "\n",
    "<p>你需要按照以下要求，给这些孩子分发糖果：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个孩子至少分配到 <code>1</code> 个糖果。</li>\n",
    "\t<li>相邻两个孩子评分更高的孩子会获得更多的糖果。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你给每个孩子分发糖果，计算并返回需要准备的 <strong>最少糖果数目</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ratings = [1,0,2]\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>ratings = [1,2,2]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。\n",
    "     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == ratings.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= ratings[i] &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [candy](https://leetcode.cn/problems/candy/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [candy](https://leetcode.cn/problems/candy/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,2]', '[1,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        # [1, queries[i][2]]\n",
    "        # for eating t type candy\n",
    "        # fastest floor(sum[t]) + 1\n",
    "        # slowest sum[t+1]\n",
    "        n = len(candiesCount)\n",
    "        m = len(queries)\n",
    "        presum = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            presum[i] = presum[i-1] + candiesCount[i-1]\n",
    "        ans = [False] * m\n",
    "        for i in range(m):\n",
    "            t = queries[i][0]\n",
    "            d = queries[i][1] + 1\n",
    "            c = queries[i][2]\n",
    "            a = presum[t] // c + 1\n",
    "            b = presum[t+1]\n",
    "            ans[i] = a <= d and d <= b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        presum = [0]\n",
    "        for candy in candiesCount:\n",
    "            presum.append(presum[-1] + candy)\n",
    "        result = []\n",
    "        for favoriteType, favoriteDay, dailyCap in queries:\n",
    "            left, right = favoriteDay+1, (favoriteDay+1)*dailyCap\n",
    "            lower, upper = presum[favoriteType]+1, presum[favoriteType+1]\n",
    "            result.append(not (right < lower or left > upper))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "        res = []\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "        for candyType, day, cap in queries:\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        for i in range(len(candiesCount)):\n",
    "\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "\n",
    "        for candyType, day, cap in queries:\n",
    "\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        accs = [0]\n",
    "        for candy in candiesCount:\n",
    "            accs.append(accs[-1] + candy)\n",
    "        answer = [False] * len(queries)\n",
    "        for i, (ftype, fday, daycap) in enumerate(queries):\n",
    "            if fday * daycap + daycap - 1 >= accs[ftype] and accs[ftype + 1] >= fday + 1:\n",
    "                answer[i] = True\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "        res = []\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "        for candyType, day, cap in queries:\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:\n",
    "        preSum = [0] * (len(candiesCount) + 1)\n",
    "        res = []\n",
    "        for i in range(len(candiesCount)):\n",
    "            preSum[i+1] = preSum[i] + candiesCount[i]\n",
    "        for candyType, day, cap in queries:\n",
    "            min_cap, max_cap = day + 1, cap * (day + 1)\n",
    "            first_candy,last_candy = preSum[candyType] + 1, preSum[candyType] + candiesCount[candyType]\n",
    "            res.append(min_cap <= last_candy and max_cap >= first_candy)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        res: List[int] = []\n",
    "        i: int = 0\n",
    "        j: int = 0\n",
    "        pick: int = 0\n",
    "            \n",
    "        while i < len(a) and j < len(b):\n",
    "            if a[i] < b[j]:\n",
    "                pick = a[i]\n",
    "                i += 1\n",
    "            elif b[j] < a[i]:\n",
    "                pick = b[j]\n",
    "                j += 1\n",
    "            else:  # a[i] == b[j]\n",
    "                pick = a[i]\n",
    "                i, j = i + 1, j + 1\n",
    "            res.append(pick)\n",
    "            \n",
    "        while i < len(a):\n",
    "            res.append(a[i])\n",
    "            i += 1\n",
    "        while j < len(b):\n",
    "            res.append(b[j])\n",
    "            j += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "    def crush(self, board: List[List[int]]) -> bool:\n",
    "        crushed: bool = False\n",
    "        pat_begin: int = 0\n",
    "        pat_end: int = 0\n",
    "\n",
    "        del_col1: List[List[int]] = [[] for _ in range(len(board[0]))]\n",
    "        for r in range(len(board)):\n",
    "            pat_begin = 0\n",
    "\n",
    "            while pat_begin < len(board[r]) - 2:\n",
    "                if board[r][pat_begin] == 0:\n",
    "                    pat_begin += 1\n",
    "                    continue\n",
    "\n",
    "                pat_end = pat_begin + 1\n",
    "                while (\n",
    "                    pat_end < len(board[r])\n",
    "                    and board[r][pat_end] == board[r][pat_begin]\n",
    "                ):\n",
    "                    pat_end += 1\n",
    "\n",
    "                if pat_end - pat_begin >= 3:\n",
    "                    for c in range(pat_begin, pat_end):\n",
    "                        del_col1[c].append(r)\n",
    "\n",
    "                pat_begin = pat_end\n",
    "                \n",
    "        del_col2: List[List[int]] = [[] for _ in range(len(board[0]))]\n",
    "        for c in range(len(board[0])):\n",
    "            pat_begin = 0\n",
    "            \n",
    "            while pat_begin < len(board) - 2:\n",
    "                if board[pat_begin][c] == 0:\n",
    "                    pat_begin += 1\n",
    "                    continue\n",
    "\n",
    "                pat_end = pat_begin + 1\n",
    "                while (\n",
    "                    pat_end < len(board)\n",
    "                    and board[pat_end][c] == board[pat_begin][c]\n",
    "                ):\n",
    "                    pat_end += 1\n",
    "\n",
    "                if pat_end - pat_begin >= 3:\n",
    "                    for r in range(pat_begin, pat_end):\n",
    "                        del_col2[c].append(r)\n",
    "\n",
    "                pat_begin = pat_end\n",
    "\n",
    "        w: int = 0\n",
    "        r: int = 0\n",
    "        to_del: List[int] = []\n",
    "\n",
    "        for c in range(len(board[0])):\n",
    "            to_del = self.merge(del_col1[c], del_col2[c])\n",
    "            if len(to_del) == 0:\n",
    "                continue\n",
    "\n",
    "            crushed = True\n",
    "            w, r = to_del[-1], to_del[-1]\n",
    "            while len(to_del) > 0:\n",
    "                if r == to_del[-1]:\n",
    "                    to_del.pop()\n",
    "                else:\n",
    "                    board[w][c] = board[r][c]\n",
    "                    w -= 1\n",
    "                r -= 1\n",
    "            while r >= 0:\n",
    "                board[w][c] = board[r][c]\n",
    "                r, w = r - 1, w - 1\n",
    "            while w >= 0:\n",
    "                board[w][c] = 0\n",
    "                w -= 1\n",
    "\n",
    "        return crushed\n",
    "\n",
    "\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        while self.crush(board):\n",
    "            pass\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        f=0\n",
    "        while True:\n",
    "            f=0\n",
    "            for x in range(m):\n",
    "                for y in range(n-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x][y+1])==abs(board[x][y+2]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x][y+1]=-tmp\n",
    "                        board[x][y+2]=-tmp\n",
    "\n",
    "            for y in range(n):\n",
    "                for x in range(m-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x+1][y])==abs(board[x+2][y]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x+1][y]=-tmp\n",
    "                        board[x+2][y]=-tmp\n",
    "\n",
    "            if f==1:\n",
    "                for y in range(n):\n",
    "                    rr=m-1\n",
    "                    for x in range(m-1,-1,-1):\n",
    "                        if board[x][y]>=0:\n",
    "                            board[rr][y]=board[x][y]\n",
    "                            rr=rr-1\n",
    "                    while rr>=0:\n",
    "                        board[rr][y]=0\n",
    "                        rr-=1\n",
    "\n",
    "            if f==0:\n",
    "                break\n",
    "        return board\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row,column = len(board),len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(row):\n",
    "            for c in range(column-2):\n",
    "                if abs(board[r][c])==abs(board[r][c+1])==abs(board[r][c+2])!=0:\n",
    "                    board[r][c]=board[r][c+1]=board[r][c+2]=-abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(column):\n",
    "            for r in range(row-2):\n",
    "                if abs(board[r][c])==abs(board[r+1][c])==abs(board[r+2][c])!=0:\n",
    "                    board[r][c]=board[r+1][c]=board[r+2][c]=-abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(column):\n",
    "            wr = row-1\n",
    "            for r in range(row-1,-1,-1):\n",
    "                if board[r][c]>0: \n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr-=1\n",
    "            for wr in range(wr,-1,-1):\n",
    "                board[wr][c] = 0\n",
    "        \n",
    "        return self.candyCrush(board) if todo else board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def check():\n",
    "            state = [[0] * n for _ in range(m)]\n",
    "            signal = 0\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n - 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur != 0 and cur == board[i][j + 1] and cur == board[i][j + 2]:\n",
    "                        signal = 1\n",
    "                        state[i][j:j+3] = [1]*3\n",
    "                        j += 2\n",
    "                        while j + 1 < n and board[i][j + 1] == board[i][j]:\n",
    "                            state[i][j + 1] = 1\n",
    "                            j += 1\n",
    "                    j += 1\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                while i >= 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur == 0:\n",
    "                        break\n",
    "                    if cur == board[i - 1][j] and cur == board[i - 2][j]:\n",
    "                        signal = 1\n",
    "                        for x in range(i, i - 3, -1):\n",
    "                            state[x][j] = 1\n",
    "                        i -= 2\n",
    "                        while i >= 1 and board[i - 1][j] == board[i][j]:\n",
    "                            state[i - 1][j] = 1\n",
    "                            i -= 1\n",
    "                    i -= 1\n",
    "            return state, signal\n",
    "        \n",
    "        def revise(state):\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                pos = m - 1\n",
    "                while pos >= 0:\n",
    "                    if state[pos][j] != 1:\n",
    "                        board[i][j] = board[pos][j]\n",
    "                        i -= 1\n",
    "                    pos -= 1\n",
    "                while i >= 0 and board[i][j] != 0:\n",
    "                    board[i][j] = 0\n",
    "                    i -= 1\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            sta, sig = check()\n",
    "            if sig == 0:\n",
    "                return board\n",
    "            revise(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Repeatedly until the board is stable:\n",
    "        Find the candies to crush:\n",
    "            Iterate through the board and for each cell, check if it starts a row or column of 3 candies of the same type.\n",
    "            Mark the candies to crush in-place by setting their value to negative.\n",
    "        Crush and drop the candies:\n",
    "            Iterate through the board by ascending column and descending row.\n",
    "            Keep track of the number of empty cells in the current column and drop the candies above by that number.\n",
    "    Time complexity: O(mn * mn) (loose upper bound). Space complexity: O(1).\n",
    "    '''\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            stable = True\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if i + 2 < m and abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i + 1][j] = board[i + 2][j] = -abs(board[i][j])\n",
    "                    if j + 2 < n and abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i][j + 1] = board[i][j + 2] = -abs(board[i][j])\n",
    "            \n",
    "            if stable:\n",
    "                return board\n",
    "                \n",
    "            for j in range(n):\n",
    "                numEmpty = 0\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] <= 0:\n",
    "                        board[i][j] = 0\n",
    "                        numEmpty += 1\n",
    "                    else:\n",
    "                        board[i][j], board[i+numEmpty][j] = board[i+numEmpty][j], board[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        def bfs(i, j):\n",
    "            v = board[i][j]\n",
    "            visited = set()\n",
    "            # Test row\n",
    "            row_candies = []\n",
    "            x = i\n",
    "            while x < m and board[x][j] == v:\n",
    "                row_candies.append((x, j))\n",
    "                x += 1\n",
    "            if len(row_candies) >= 3:\n",
    "                visited.update(row_candies)\n",
    "            # Test column\n",
    "            column_candies = []\n",
    "            y = j\n",
    "            while y < n and board[i][y] == v:\n",
    "                column_candies.append((i, y))\n",
    "                y += 1\n",
    "            if len(column_candies) >= 3:\n",
    "                visited.update(column_candies)\n",
    "            return visited\n",
    "\n",
    "        while True:\n",
    "            # Judge what grids will be crushed\n",
    "            drop = [[0] * n for _ in range(m)]\n",
    "            should_drop = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    visited = bfs(i, j)\n",
    "                    if len(visited) >= 3:\n",
    "                        for x, y in visited:\n",
    "                            drop[x][y] = 1\n",
    "                            should_drop = True\n",
    "            if not should_drop:\n",
    "                return board\n",
    "\n",
    "            # Crush and drop each column\n",
    "            for j in range(n):\n",
    "                bottom = m - 1\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    if drop[i][j] == 1:\n",
    "                        continue\n",
    "                    board[bottom][j] = board[i][j]\n",
    "                    bottom -= 1\n",
    "                while bottom != -1:\n",
    "                    board[bottom][j] = 0\n",
    "                    bottom -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "#         def in_board(i, j):\n",
    "#             if i < len(board) and i >= 0 and j < len(board[0]) and j >= 0:\n",
    "#                 return True\n",
    "#             return False\n",
    "        \n",
    "#         def check_adjacent(board, i, j):\n",
    "#             dirs = [(1,0), (-1,0), (0,1), (0,-1)]\n",
    "#             cur_val = board[i][j]\n",
    "#             board[i][j] = 0\n",
    "#             temp_list = []\n",
    "#             for dir in dirs:\n",
    "#                 cur_i = i + dir[0]\n",
    "#                 cur_j = j + dir[1]\n",
    "#                 if in_board(cur_i, cur_j) and board[cur_i][cur_j] == cur_val:\n",
    "#                     temp_list = temp_list + check_adjacent(board, cur_i, cur_j)\n",
    "#             temp_list.append((i, j))\n",
    "#             return temp_list\n",
    "        \n",
    "#         def drop_board(): # todo update algorithm if possible\n",
    "#             for j in range(len(board[0])-1, -1, -1):\n",
    "#                 for i in range(len(board)-1, -1, -1):\n",
    "#                     if board[i][j] == 0:\n",
    "#                         board[0][j] = 0\n",
    "#                         for k in range(1, i + 1):\n",
    "#                             board[k][j] = board[k-1][j]\n",
    "#         def print_board():\n",
    "#             for i in range(len(board)):\n",
    "#                 for j in range(len(board[0])):\n",
    "#                     print(board[i][j], end=\" \")\n",
    "#                 print(\"\")\n",
    "\n",
    "        \n",
    "#         while True:\n",
    "#             prev_board = copy.deepcopy(board)\n",
    "#             # check\n",
    "#             for i in range(len(board)):\n",
    "#                 for j in range(len(board[0])):\n",
    "#                     if board[i][j] != 0:\n",
    "#                         temp_list = check_adjacent(board[:][:], i, j)\n",
    "#                         print(f\"temp_list : {temp_list}\")\n",
    "#                         if len(temp_list) >= 3:\n",
    "#                             for loc in temp_list:\n",
    "#                                 board[loc[0]][loc[1]] = 0\n",
    "#             print(\"board before dropping\")\n",
    "#             print_board()\n",
    "#             # drop\n",
    "#             drop_board()\n",
    "#             print(\"board after dropping\")\n",
    "#             print_board()\n",
    "\n",
    "#             if prev_board == board:\n",
    "#                 break\n",
    "#         return board\n",
    "        \n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        while need_todo:\n",
    "            need_todo = False\n",
    "            for r in range(row):\n",
    "                for c in range(col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs (board[r][c+2]):\n",
    "                        need_todo = True \n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c] = tmp \n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp \n",
    "            for c in range(col):\n",
    "                for r in range(row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True \n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c] = tmp \n",
    "                        board[r+1][c] = tmp \n",
    "                        board[r+2][c] = tmp \n",
    "            if need_todo == True:\n",
    "                for c in range(col):\n",
    "                    rr = row - 1\n",
    "                    for r in range(row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        Row, Col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        ################ 注意L形也是可以的\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\n",
    "            need_todo = False\n",
    "            #### 先搞定行\n",
    "            for r in range(Row):\n",
    "                for c in range(Col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\n",
    "                        need_todo = True\n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp\n",
    "            #### 再搞定列\n",
    "            for c in range(Col):\n",
    "                for r in range(Row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True\n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r+1][c] = tmp\n",
    "                        board[r+2][c] = tmp\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\n",
    "            if need_todo == True:\n",
    "                for c in range(Col):\n",
    "                    rr = Row - 1\n",
    "                    for r in range(Row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m,n,mark=len(board),len(board[0]),True\n",
    "        while mark:\n",
    "            mark=False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j]==0:\n",
    "                        continue\n",
    "                    if j<n-2 and abs(board[i][j])==abs(board[i][j+1])==abs(board[i][j+2]):\n",
    "                        val=-abs(board[i][j])\n",
    "                        board[i][j]=val\n",
    "                        board[i][j+1]=val\n",
    "                        board[i][j+2]=val\n",
    "                        mark=True\n",
    "                    if i<m-2 and abs(board[i][j])==abs(board[i+1][j])==abs(board[i+2][j]):\n",
    "                        mark=True\n",
    "                        val=-abs(board[i][j])\n",
    "                        board[i][j]=val\n",
    "                        board[i+1][j]=val\n",
    "                        board[i+2][j]=val\n",
    "                        mark=True\n",
    "            for j in range(n):\n",
    "                cursor=m-1\n",
    "                for i in range(m-1,-1,-1):\n",
    "                    if board[i][j]>0:\n",
    "                        board[cursor][j]=board[i][j]\n",
    "                        cursor-=1\n",
    "                for i in range(cursor,-1,-1):\n",
    "                    board[i][j]=0\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C - 2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m,n=len(board),len(board[0])\n",
    "        xiao=set()\n",
    "        def bl():\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if isKill(i,j):\n",
    "                        xiao.add((i,j))\n",
    "            if len(xiao)==0:\n",
    "                return False\n",
    "            return True\n",
    "        def isKill(i,j):\n",
    "            t=board[i][j]\n",
    "            if t==0:\n",
    "                return False\n",
    "            if i+2<m and board[i+1][j]==t and board[i+2][j]==t:\n",
    "                return True\n",
    "            if i+1<m and i-1>=0 and board[i-1][j]==t and board[i+1][j]==t:\n",
    "                return True\n",
    "            if i-2>=0 and board[i-2][j]==t and board[i-1][j]==t:\n",
    "                return True\n",
    "            if j+2<n and board[i][j+2]==t and board[i][j+1]==t:\n",
    "                return True\n",
    "            if j+1<n and j-1>=0 and board[i][j+1]==t and board[i][j-1]==t:\n",
    "                return True\n",
    "            if j-2>=0 and board[i][j-2]==t and board[i][j-1]==t:\n",
    "                return True\n",
    "            return False\n",
    "        def xxc(i,j):\n",
    "            for t in range(i,-1,-1):\n",
    "                if t==0:\n",
    "                    board[t][j]=0\n",
    "                else:\n",
    "                    board[t][j]=board[t-1][j]\n",
    "        def xc():\n",
    "            ltxiao=list(xiao)\n",
    "            ltxiao=sorted(ltxiao,key= lambda k:k[0],reverse=False)\n",
    "            # print(ltxiao)\n",
    "            for i,j in ltxiao:\n",
    "                xxc(i,j)\n",
    "        while(bl()):\n",
    "            xc()\n",
    "            xiao=set()\n",
    "        # for i in board:\n",
    "        #     print(i)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        return self.answer_1(board)\n",
    "\n",
    "    def answer_1(self, board):\n",
    "        row_len = len(board)\n",
    "        col_len = len(board[0])\n",
    "\n",
    "        to_do = False\n",
    "\n",
    "        # 标记\n",
    "        for row_index in range(row_len):\n",
    "            for col_index in range(col_len - 2):\n",
    "                current_num = abs(board[row_index][col_index])\n",
    "                second_num = abs(board[row_index][col_index + 1])\n",
    "                third_num = abs(board[row_index][col_index + 2])\n",
    "\n",
    "                if not (current_num == second_num == third_num and current_num != 0):\n",
    "                    continue\n",
    "\n",
    "                to_do = True\n",
    "\n",
    "                board[row_index][col_index] = -current_num\n",
    "                board[row_index][col_index + 1] = -current_num\n",
    "                board[row_index][col_index + 2] = -current_num\n",
    "\n",
    "        for row_index in range(row_len - 2):\n",
    "            for col_index in range(col_len):\n",
    "                current_num = abs(board[row_index][col_index])\n",
    "                second_num = abs(board[row_index + 1][col_index])\n",
    "                third_num = abs(board[row_index + 2][col_index])\n",
    "\n",
    "                if not (current_num == second_num == third_num and current_num != 0):\n",
    "                    continue\n",
    "\n",
    "                to_do = True\n",
    "\n",
    "                board[row_index][col_index] = -current_num\n",
    "                board[row_index + 1][col_index] = -current_num\n",
    "                board[row_index + 2][col_index] = -current_num\n",
    "\n",
    "        # 清除\n",
    "        for col_index in range(col_len):\n",
    "            tmp_row_index = row_len - 1\n",
    "            for row_index in range(row_len - 1, -1, -1):\n",
    "                if board[row_index][col_index] > 0:\n",
    "                    board[tmp_row_index][col_index] = board[row_index][col_index]\n",
    "                    tmp_row_index -= 1\n",
    "\n",
    "            for row_index in range(tmp_row_index , -1, -1):\n",
    "                board[row_index][col_index] = 0\n",
    "        return self.answer_1(board) if to_do else board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        f=0\n",
    "        while True:\n",
    "            f=0\n",
    "            for x in range(m):\n",
    "                for y in range(n-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x][y+1])==abs(board[x][y+2]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x][y+1]=-tmp\n",
    "                        board[x][y+2]=-tmp\n",
    "\n",
    "            for y in range(n):\n",
    "                for x in range(m-2):\n",
    "                    if board[x][y]!=0 and abs(board[x][y])==abs(board[x+1][y])==abs(board[x+2][y]):\n",
    "                        tmp=abs(board[x][y])\n",
    "                        f=1\n",
    "                        board[x][y]=-tmp\n",
    "                        board[x+1][y]=-tmp\n",
    "                        board[x+2][y]=-tmp\n",
    "\n",
    "            if f==1:\n",
    "                for y in range(n):\n",
    "                    rr=m-1\n",
    "                    for x in range(m-1,-1,-1):\n",
    "                        if board[x][y]>0:\n",
    "                            board[rr][y]=board[x][y]\n",
    "                            rr=rr-1\n",
    "                    while rr>=0:\n",
    "                        board[rr][y]=0\n",
    "                        rr-=1\n",
    "\n",
    "            if f==0:\n",
    "                break\n",
    "        return board\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board):\n",
    "        # 消除过程分为两步，一是将可消除部分置为零，二是将空位上方的部分落下\n",
    "        m, n = len(board), len(board[0])\n",
    "        mem = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def crush():\n",
    "            flg, flg1 = 0, 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    x0, y0 = 0, 0\n",
    "                    for x in range(i + 1, m):\n",
    "                        if board[i][j] != 0 and board[x][j] == board[i][j]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            if board[i][j] == 0 or x - i <= 2:\n",
    "                                pass\n",
    "                            else:\n",
    "                                for t in range(i, x):\n",
    "                                    mem[t][j] = 1\n",
    "                                flg = 1\n",
    "                                x0 = 1\n",
    "                            break\n",
    "                    else:\n",
    "                        if board[i][j] != 0 and m - i > 2 and x0 != 1:\n",
    "                            for t in range(i, m):\n",
    "                                mem[t][j] = 1\n",
    "                            flg = 1\n",
    "                    for y in range(j + 1, n):\n",
    "                        if board[i][j] != 0 and board[i][y] == board[i][j]:\n",
    "                            pass\n",
    "                        else:\n",
    "                            if board[i][j] == 0 or y - j <= 2:\n",
    "                                pass\n",
    "                            else:\n",
    "                                for t in range(j, y):\n",
    "                                    mem[i][t] = 1\n",
    "                                flg1 = 1\n",
    "                                y0 = 1\n",
    "                            break\n",
    "                    else:\n",
    "                        if board[i][j] != 0 and n - j > 2 and y0 != 1:\n",
    "                            for t in range(j, n):\n",
    "                                mem[i][t] = 1\n",
    "                            flg1 = 1\n",
    "            if flg == 1 or flg1 == 1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def fall():\n",
    "            for j in range(n):\n",
    "                # for i in range(m - 2, -1, -1):\n",
    "                #     if mem[i + 1][j] == 1:\n",
    "                #         mem[i + 1][j] = 0\n",
    "                #         mem[i][j] = 1\n",
    "                #         board[i + 1][j] = board[i][j]\n",
    "                #         board[i][j] = 0\n",
    "                # 首先找到底，即最底的1，然后找到下落点，即最底的0，将下落点置为1，将底置为0；底往上走\n",
    "                i1, i2 = m - 1, m - 1\n",
    "                while i1 >= 0:\n",
    "                    if mem[i1][j] == 1:\n",
    "                        i2 = i1 - 1\n",
    "                        while i2 >= 0 and mem[i2][j] != 0:\n",
    "                            i2 -= 1\n",
    "                        if i2 < 0:\n",
    "                            board[i1][j] = 0\n",
    "                        else:\n",
    "                            board[i1][j] = board[i2][j]\n",
    "                            board[i2][j] = 0\n",
    "                            mem[i1][j] = 0\n",
    "                            mem[i2][j] = 1\n",
    "                    i1 -= 1\n",
    "\n",
    "        i = 0\n",
    "        while crush() and i < 50:\n",
    "            fall()\n",
    "            i += 1\n",
    "        return board\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "\n",
    "        remove = [[False] * m for _ in range(n)]\n",
    "        todo = True\n",
    "        # first mark the elements to be eliminated horizontally\n",
    "        while todo:\n",
    "            todo = False\n",
    "            for r in range(n):\n",
    "                left = 0\n",
    "                right = 0\n",
    "                while left < m:\n",
    "                    while right < m and board[r][left] == board[r][right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right - left >= 3 and board[r][left] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(left, right):\n",
    "                            remove[r][idx] = True\n",
    "                    left = right\n",
    "    \n",
    "            # second mark the elements to be eliminated vertically\n",
    "            for c in range(m):\n",
    "                up = 0\n",
    "                down = 0\n",
    "                while up < n:\n",
    "                    while down < n and board[up][c] == board[down][c]:\n",
    "                        down += 1\n",
    "                    \n",
    "                    if down - up >= 3 and board[up][c] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(up, down):\n",
    "                            remove[idx][c] = True\n",
    "                    up = down\n",
    "            \n",
    "            # vertically squash every removed element row by row from bottom to top\n",
    "            for r in range(n - 1, -1, -1):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        index = r\n",
    "                        while index >= 0 and remove[index][c] and board[index][c] != 0:\n",
    "                            index -= 1\n",
    "                        if index >= 0:\n",
    "                            board[r][c] = board[index][c]\n",
    "                            remove[r][c] = False\n",
    "                            remove[index][c] = True\n",
    "            \n",
    "            for r in range(n):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        board[r][c] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        def check(board_):\n",
    "            # 检查是存在能够消除的格子并标记\n",
    "            flags = [[0]*n for _ in range(m)]\n",
    "            f = False\n",
    "            # 先检查行\n",
    "            for i in range(m):\n",
    "                for j in range(n-2):\n",
    "                    if board_[i][j]==board_[i][j+1]==board_[i][j+2]!=0:\n",
    "                        flags[i][j]=1\n",
    "                        flags[i][j+1]=1\n",
    "                        flags[i][j+2]=1\n",
    "                        f = True\n",
    "            # 检查列\n",
    "            for j in range(n):\n",
    "                for i in range(m-2):\n",
    "                    if board_[i][j]==board_[i+1][j]==board_[i+2][j]!=0:\n",
    "                        flags[i][j]=1\n",
    "                        flags[i+1][j]=1\n",
    "                        flags[i+2][j]=1\n",
    "                        f = True\n",
    "            return f, flags\n",
    "        \n",
    "        def ruin(board_, flags):\n",
    "            for j in range(n):\n",
    "                # 按列写回糖果\n",
    "                read = m-1\n",
    "                write = m-1\n",
    "                while write>=0:\n",
    "                    while read >= 0 and flags[read][j]==1:\n",
    "                        read -= 1\n",
    "                    \n",
    "                    if read < 0:\n",
    "                        board_[write][j] = 0\n",
    "                    else:\n",
    "                        board_[write][j] = board_[read][j]\n",
    "                    write -= 1\n",
    "                    read -= 1\n",
    "            return board_\n",
    "\n",
    "        while True:\n",
    "            f, flag = check(board)\n",
    "            if f:\n",
    "                board = ruin(board, flag)\n",
    "            else:\n",
    "                return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        def update():\n",
    "            stable = True\n",
    "\n",
    "            # 获取待粉碎的糖果\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n:\n",
    "                    if board[i][j] == 0:\n",
    "                        j += 1\n",
    "                        continue\n",
    "                    v = abs(board[i][j])\n",
    "                    k = j + 1\n",
    "                    while k < n and abs(board[i][k]) == v:\n",
    "                        k += 1\n",
    "                    if k - j >= 3:\n",
    "                        stable = False\n",
    "                        for jj in range(j, k):\n",
    "                            board[i][jj] = -v\n",
    "                    j = k\n",
    "            for j in range(n):\n",
    "                i = 0\n",
    "                while i < m:\n",
    "                    if board[i][j] == 0:\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    v = abs(board[i][j])\n",
    "                    k = i + 1\n",
    "                    while k < m and abs(board[k][j]) == v:\n",
    "                        k += 1\n",
    "                    if k - i >= 3:\n",
    "                        stable = False\n",
    "                        for ii in range(i, k):\n",
    "                            board[ii][j] = -v\n",
    "                    i = k\n",
    "            \n",
    "            if stable:\n",
    "                return\n",
    "\n",
    "            # 更新\n",
    "            for j in range(n):\n",
    "                i0 = i1 = m - 1\n",
    "                while i1 >= 0:\n",
    "                    if board[i1][j] < 0:\n",
    "                        i1 -= 1\n",
    "                        continue\n",
    "                    board[i0][j] = board[i1][j]\n",
    "                    i0 -= 1\n",
    "                    i1 -= 1\n",
    "                for i1 in range(i0, -1, -1):\n",
    "                    board[i1][j] = 0\n",
    "            \n",
    "            update()\n",
    "        \n",
    "        update()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        while True:\n",
    "            marked=self.mark(board)\n",
    "            # 没办法碾碎糖果,并且没有值为负数\n",
    "            if not marked:\n",
    "                return board\n",
    "            else: self.crush(board)\n",
    "            \n",
    "    \n",
    "    def mark(self,board:List[List[int]])->bool:\n",
    "        marked=False\n",
    "        m,n=len(board),len(board[0])\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if c>=1 and c<n-1 and abs(board[r][c])==abs(board[r][c-1])==abs(board[r][c+1]) and abs(board[r][c])!=0:\n",
    "                    board[r][c]=board[r][c-1]=board[r][c+1]=-abs(board[r][c])\n",
    "                    marked=True\n",
    "        for c in range(n):\n",
    "            for r in range(m):\n",
    "                if r>=1 and r<m-1 and abs(board[r][c])==abs(board[r-1][c])==abs(board[r+1][c]) and abs(board[r][c])!=0:\n",
    "                    board[r][c]=board[r-1][c]=board[r+1][c]=-abs(board[r][c])\n",
    "                    marked=True\n",
    "        return marked\n",
    "\n",
    "    def crush(self,board:List[List[int]]):\n",
    "        m,n=len(board),len(board[0])\n",
    "        for c in range(n):\n",
    "            cur_r=m-1\n",
    "            for r in range(m-1,-1,-1):\n",
    "                if board[r][c]>0:\n",
    "                    board[cur_r][c]=board[r][c]\n",
    "                    cur_r-=1\n",
    "            while cur_r>=0:\n",
    "                board[cur_r][c]=0\n",
    "                cur_r-=1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        # def crush():\n",
    "        #     to_crush = set()\n",
    "        #     # 行\n",
    "        #     for i in range(m):\n",
    "        #         j1, j2 = 0, 0\n",
    "        #         while j2 <= n:\n",
    "        #             if j2 == n or board[i][j2] != board[i][j1]:\n",
    "        #                 if j2 - j1 >= 3 and board[i][j1] > 0:\n",
    "        #                     for k in range(j1, j2):\n",
    "        #                         to_crush.add((i, k))\n",
    "        #                 j1 = j2\n",
    "        #             j2 += 1\n",
    "        #     # 列\n",
    "        #     for j in range(n):\n",
    "        #         i1, i2 = 0, 0\n",
    "        #         while i2 <= m:\n",
    "        #             if i2 == m or board[i1][j] != board[i2][j]:\n",
    "        #                 if i2 - i1 >= 3 and board[i1][j] > 0:\n",
    "        #                     for k in range(i1, i2):\n",
    "        #                         to_crush.add((k, j))\n",
    "        #                 i1 = i2\n",
    "        #             i2 += 1\n",
    "        #     for i, j in to_crush:\n",
    "        #         board[i][j] = 0\n",
    "        #     return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        label = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n - 2):\n",
    "                if abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2]) != 0:\n",
    "                    board[i][j] = board[i][j+1] = board[i][j+2] = -abs(board[i][j])\n",
    "                    label = 1\n",
    "        for j in range(n):\n",
    "            for i in range(m - 2):\n",
    "                if abs(board[i][j]) == abs(board[i+1][j]) == abs(board[i+2][j]) != 0:\n",
    "                    board[i][j] = board[i+1][j] = board[i+2][j] = -abs(board[i][j])\n",
    "                    label = 1     \n",
    "        for j in range(n):\n",
    "            wr = m-1\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if board[i][j] > 0:\n",
    "                    board[wr][j] = board[i][j]\n",
    "                    wr -= 1\n",
    "            for i in range(wr, -1, -1):\n",
    "                board[i][j] = 0\n",
    "        if label:\n",
    "            return self.candyCrush(board)\n",
    "        else:\n",
    "            return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row = len(board)\n",
    "        col = len(board[0])\n",
    "        stable = None\n",
    "        while not stable:\n",
    "            stable = True\n",
    "            # check column axis lines\n",
    "            for r in range(row):\n",
    "                for c in range(col-2):\n",
    "                    if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                        board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                        stable = False\n",
    "            # check row axis lines\n",
    "            for r in range(row-2):\n",
    "                for c in range(col):\n",
    "                    if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                        board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                        stable = False\n",
    "            # for each column, from bottom to top eliminate the negative values\n",
    "            for c in range(col):\n",
    "                row_ptr = row - 1\n",
    "                for r in range(row-1, -1, -1):\n",
    "                    if board[r][c] > 0:\n",
    "                        board[row_ptr][c] = board[r][c]\n",
    "                        row_ptr -= 1\n",
    "                for remain in range(row_ptr, -1, -1):\n",
    "                    board[remain][c] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def check():\n",
    "            signal = 0\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n - 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur != 0 and cur == board[i][j + 1] and cur == board[i][j + 2]:\n",
    "                        signal = 1\n",
    "                        state[i][j:j+3] = [1]*3\n",
    "                        j += 2\n",
    "                        while j + 1 < n and board[i][j + 1] == board[i][j]:\n",
    "                            state[i][j + 1] = 1\n",
    "                            j += 1\n",
    "                    j += 1\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                while i >= 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur == 0:\n",
    "                        break\n",
    "                    if cur == board[i - 1][j] and cur == board[i - 2][j]:\n",
    "                        signal = 1\n",
    "                        for x in range(i, i - 3, -1):\n",
    "                            state[x][j] = 1\n",
    "                        i -= 2\n",
    "                        while i >= 1 and board[i - 1][j] == board[i][j]:\n",
    "                            state[i - 1][j] = 1\n",
    "                            i -= 1\n",
    "                    i -= 1\n",
    "            return state, signal\n",
    "        \n",
    "        def revise(state):\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                pos = m - 1\n",
    "                while pos >= 0:\n",
    "                    if state[pos][j] != 1:\n",
    "                        board[i][j] = board[pos][j]\n",
    "                        i -= 1\n",
    "                    state[pos][j] = 0\n",
    "                    pos -= 1\n",
    "                while i >= 0 and board[i][j] != 0:\n",
    "                    board[i][j] = 0\n",
    "                    i -= 1\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        state = [[0] * n for _ in range(m)]\n",
    "        while True:\n",
    "            sta, sig = check()\n",
    "            if sig == 0:\n",
    "                return board\n",
    "            revise(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        Row, Col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        ################ 注意L形也是可以的\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\n",
    "            need_todo = False\n",
    "            #### 先搞定行\n",
    "            for r in range(Row):\n",
    "                for c in range(Col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\n",
    "                        need_todo = True\n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp\n",
    "            #### 再搞定列\n",
    "            for c in range(Col):\n",
    "                for r in range(Row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True\n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r+1][c] = tmp\n",
    "                        board[r+2][c] = tmp\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\n",
    "            if need_todo == True:\n",
    "                for c in range(Col):\n",
    "                    rr = Row - 1\n",
    "                    for r in range(Row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "     def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Repeatedly until the board is stable:\n",
    "        Find the candies to crush:\n",
    "            Iterate through the board and for each cell, check if it starts a row or column of 3 candies of the same type.\n",
    "            Mark the candies to crush in-place by setting their value to negative.\n",
    "        Crush and drop the candies:\n",
    "            Iterate through the board by ascending column and descending row.\n",
    "            Keep track of the number of empty cells in the current column and drop the candies above by that number.\n",
    "    Time complexity: O(mn * mn) (loose upper bound). Space complexity: O(1).\n",
    "    '''\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            stable = True\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if i + 2 < m and abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i + 1][j] = board[i + 2][j] = -abs(board[i][j])\n",
    "                    if j + 2 < n and abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]):\n",
    "                        stable = False\n",
    "                        board[i][j] = board[i][j + 1] = board[i][j + 2] = -abs(board[i][j])\n",
    "            \n",
    "            if stable:\n",
    "                break\n",
    "                \n",
    "            for j in range(n):\n",
    "                numEmpty = 0\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] <= 0:\n",
    "                        board[i][j] = 0\n",
    "                        numEmpty += 1\n",
    "                    else:\n",
    "                        board[i][j], board[i+numEmpty][j] = board[i+numEmpty][j], board[i][j]\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            rowset, colset, locset = set(), set(), set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] != 0:\n",
    "                        if i * 100 + j not in rowset:\n",
    "                            j2 = j\n",
    "                            while j2 < n and board[i][j2] == board[i][j]:\n",
    "                                j2 += 1\n",
    "                            if j2 - j > 2:\n",
    "                                for x in range(j, j2):\n",
    "                                    loc = i * 100 + x\n",
    "                                    locset.add(loc)\n",
    "                                    rowset.add(loc)\n",
    "                        if i * 100 + j not in colset:\n",
    "                            i2 = i\n",
    "                            while i2 < m and board[i2][j] == board[i][j]:\n",
    "                                i2 += 1\n",
    "                            if i2 - i > 2:\n",
    "                                for x in range(i, i2):\n",
    "                                    loc = x * 100 + j\n",
    "                                    locset.add(loc)\n",
    "                                    colset.add(loc)\n",
    "            if len(locset) == 0:\n",
    "                return board\n",
    "            for loc in locset:\n",
    "                board[loc // 100][loc % 100] = 0\n",
    "            for j in range(n):\n",
    "                zeroi = m - 1\n",
    "                while zeroi > -1 and board[zeroi][j] != 0:\n",
    "                    zeroi -= 1\n",
    "                for i in range(zeroi - 1, -1, -1):\n",
    "                    if board[i][j] != 0:\n",
    "                        board[zeroi][j] = board[i][j]\n",
    "                        board[i][j] = 0\n",
    "                        zeroi -= 1\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        def crush():\n",
    "            cnt = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i >= 2 and abs(board[i-2][j]) == abs(board[i-1][j]) == abs(board[i][j]) != 0:\n",
    "                        c = abs(board[i][j])\n",
    "                        board[i-2][j] = board[i-1][j] = board[i][j] = - c\n",
    "                        cnt += 1\n",
    "                    if j >= 2 and abs(board[i][j-2]) == abs(board[i][j-1]) == abs(board[i][j]) != 0:\n",
    "                        c = abs(board[i][j])\n",
    "                        board[i][j-2] = board[i][j-1] = board[i][j] = - c\n",
    "                        cnt += 1\n",
    "            return cnt \n",
    "        def check():\n",
    "            for j in range(n):\n",
    "                to_fill = m-1\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] > 0:\n",
    "                        tmp = board[i][j]\n",
    "                        board[i][j] = 0\n",
    "                        board[to_fill][j] = abs(tmp)\n",
    "                        to_fill -= 1\n",
    "                    else:\n",
    "                        board[i][j] = 0\n",
    "\n",
    "        # i = 0\n",
    "        while True:\n",
    "            c = crush()\n",
    "            # print(c)\n",
    "            if c == 0:\n",
    "                return board\n",
    "            check()\n",
    "            # i += 1\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        Row, Col = len(board), len(board[0])\n",
    "        need_todo = True\n",
    "        ################ 注意L形也是可以的\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\n",
    "            need_todo = False\n",
    "            #### 先搞定行\n",
    "            for r in range(Row):\n",
    "                for c in range(Col - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\n",
    "                        need_todo = True\n",
    "                        tmp = - abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r][c+1] = tmp\n",
    "                        board[r][c+2] = tmp\n",
    "            #### 再搞定列\n",
    "            for c in range(Col):\n",
    "                for r in range(Row - 2):\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\n",
    "                        need_todo = True\n",
    "                        tmp = -abs(board[r][c])\n",
    "                        board[r][c]   = tmp\n",
    "                        board[r+1][c] = tmp\n",
    "                        board[r+2][c] = tmp\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\n",
    "            if need_todo == True:\n",
    "                for c in range(Col):\n",
    "                    rr = Row - 1\n",
    "                    for r in range(Row - 1, -1, -1):\n",
    "                        if board[r][c] > 0:\n",
    "                            board[rr][c] = board[r][c]\n",
    "                            rr -= 1\n",
    "                    while rr > -1:\n",
    "                        board[rr][c] = 0\n",
    "                        rr -= 1\n",
    "\n",
    "        return board\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0]) \n",
    "        vis1 = [[0] * n for _ in range(m)]\n",
    "        vis2 = [[0] * n for _ in range(m)]\n",
    "        while True:\n",
    "            flag = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue \n",
    "                    if not vis1[i][j]:\n",
    "                        tot= 1\n",
    "                        for k in range(j+1, n):\n",
    "                            if board[i][k] == board[i][k-1]:\n",
    "                                tot += 1\n",
    "                            else:\n",
    "                                break \n",
    "                        if tot >= 3:\n",
    "                            flag = 1\n",
    "                            for k in range(j, j+tot):\n",
    "                                vis1[i][k] = 1 \n",
    "                    if not vis2[i][j]:\n",
    "                        tot = 1 \n",
    "                        for k in range(i+1, m):\n",
    "                            if board[k][j] == board[k-1][j]:\n",
    "                                tot += 1\n",
    "                            else:\n",
    "                                break \n",
    "                        if tot >= 3:\n",
    "                            flag = 1\n",
    "                            for k in range(i, i+tot):\n",
    "                                vis2[k][j] = 1\n",
    "            #print(flag)\n",
    "            if flag == 0:\n",
    "                break \n",
    "            for j in range(n):\n",
    "                l = m-1\n",
    "                for r in range(m-1, -1, -1):\n",
    "                    if vis1[r][j] or vis2[r][j]:\n",
    "                        vis1[r][j] = vis2[r][j] = 0\n",
    "                        continue \n",
    "                    else:\n",
    "                        board[l][j] = board[r][j]\n",
    "                        l -= 1\n",
    "                while l >= 0:\n",
    "                    board[l][j] = 0\n",
    "                    l-=1 \n",
    "        return board \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def candyCrush(self, board):\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1, -1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for wr in range(wr, -1, -1):\n",
    "                board[wr][c] = 0\n",
    "\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R, C = len(board), len(board[0])\n",
    "        todo = False\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]) != 0:\n",
    "                    board[r][c] = board[r][c+1] = board[r][c+2] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "        for r in range(R-2):\n",
    "            for c in range(C):\n",
    "                if abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]) != 0:\n",
    "                    board[r][c] = board[r+1][c] = board[r+2][c] = -abs(board[r][c])\n",
    "                    todo = True\n",
    "        for c in range(C):\n",
    "            wr = R-1\n",
    "            for r in range(R-1, -1,-1):\n",
    "                if board[r][c] > 0:\n",
    "                    board[wr][c] = board[r][c]\n",
    "                    wr -= 1\n",
    "            for w in range(wr,-1,-1):\n",
    "                board[w][c] = 0\n",
    "        return self.candyCrush(board) if todo else board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = []\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.append((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i][j1]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.append((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def crush():\n",
    "            to_crush = set()\n",
    "            # 行\n",
    "            for i in range(m):\n",
    "                j1, j2 = 0, 0\n",
    "                while j2 <= n:\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1] > 0:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.add((i, k))\n",
    "                        j1 = j2\n",
    "                    j2 += 1\n",
    "            # 列\n",
    "            for j in range(n):\n",
    "                i1, i2 = 0, 0\n",
    "                while i2 <= m:\n",
    "                    if i2 == m or board[i1][j] != board[i2][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j] > 0:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.add((k, j))\n",
    "                        i1 = i2\n",
    "                    i2 += 1\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        row, col = len(board), len(board[0])\n",
    "        todo = True\n",
    "\n",
    "        while todo:\n",
    "            todo = False\n",
    "            # row judge\n",
    "            for i in range(row):\n",
    "                for j in range(col-2):\n",
    "                    if board[i][j] != 0 and abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2]):\n",
    "                        todo = True\n",
    "                        tmp = - abs(board[i][j])\n",
    "                        board[i][j] = tmp\n",
    "                        board[i][j+1] = tmp\n",
    "                        board[i][j+2] = tmp\n",
    "\n",
    "            # col judge\n",
    "            for j in range(col):\n",
    "                for i in range(row-2):\n",
    "                    if board[i][j] != 0 and abs(board[i][j]) == abs(board[i+1][j]) == abs(board[i+2][j]):\n",
    "                        todo = True\n",
    "                        tmp = - abs(board[i][j])\n",
    "                        board[i][j] = tmp\n",
    "                        board[i+1][j] = tmp\n",
    "                        board[i+2][j] = tmp\n",
    "\n",
    "            #fall as cols\n",
    "            if todo:\n",
    "                for j in range(col):\n",
    "                    waitRow = row - 1\n",
    "                    for i in range(row-1, -1, -1):\n",
    "                        if board[i][j] > 0:\n",
    "                            board[waitRow][j] = board[i][j]\n",
    "                            waitRow -= 1\n",
    "                    while waitRow > -1:\n",
    "                        board[waitRow][j] = 0\n",
    "                        waitRow -= 1\n",
    "\n",
    "        return board\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R,C= len(board),len(board[0])\n",
    "        #check horizontal same\n",
    "        crashed= False\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c])==abs(board[r][c+1])==abs(board[r][c+2])!=0:\n",
    "                    board[r][c]=board[r][c+1]=board[r][c+2]=-abs(board[r][c])\n",
    "                    crashed=True\n",
    "        #check vertical same\n",
    "        for c in range(C):\n",
    "            for r in range(R-2):\n",
    "                if abs(board[r][c])==abs(board[r+1][c])==abs(board[r+2][c])!=0:\n",
    "                    board[r][c]=board[r+1][c]=board[r+2][c]=-abs(board[r][c])\n",
    "                    crashed= True\n",
    "\n",
    "        for c in range(C):\n",
    "            write=R-1\n",
    "            for read in range(R-1,-1,-1):\n",
    "                newValue= board[read][c]\n",
    "                board[read][c]=0\n",
    "                if newValue>0:\n",
    "                    board[write][c]= newValue\n",
    "                    write-=1\n",
    "            # for write in range(write,-1,-1):\n",
    "            #     board[write][c]=0\n",
    "        if crashed:\n",
    "            return self.candyCrush(board)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        mark = True\n",
    "        while mark:\n",
    "            # 标记需要粉碎的糖果\n",
    "            mark = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if j < n - 2 and abs(board[i][j]) == abs(board[i][j+1]) == abs(board[i][j+2]):\n",
    "                        mark = True\n",
    "                        val = abs(board[i][j])\n",
    "                        board[i][j] = -val\n",
    "                        board[i][j+1] = -val\n",
    "                        board[i][j+2] = -val\n",
    "                    if i < m - 2 and abs(board[i][j]) == abs(board[i+1][j]) == abs(board[i+2][j]):\n",
    "                        mark = True\n",
    "                        val = abs(board[i][j])\n",
    "                        board[i][j] = -val\n",
    "                        board[i+1][j] = -val\n",
    "                        board[i+2][j] = -val\n",
    "            # 糖果下落\n",
    "            for j in range(n):\n",
    "                idx = m - 1\n",
    "                for i in range(m-1, -1, -1):\n",
    "                    if board[i][j] > 0:\n",
    "                        board[idx][j] = board[i][j]\n",
    "                        idx -= 1\n",
    "                for i in range(idx, -1, -1):\n",
    "                    board[i][j] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        R,C= len(board),len(board[0])\n",
    "        #check horizontal same\n",
    "        crashed= False\n",
    "        for r in range(R):\n",
    "            for c in range(C-2):\n",
    "                if abs(board[r][c])==abs(board[r][c+1])==abs(board[r][c+2])!=0:\n",
    "                    board[r][c]=board[r][c+1]=board[r][c+2]=-abs(board[r][c])\n",
    "                    crashed=True\n",
    "        #check vertical same\n",
    "        for c in range(C):\n",
    "            for r in range(R-2):\n",
    "                if abs(board[r][c])==abs(board[r+1][c])==abs(board[r+2][c])!=0:\n",
    "                    board[r][c]=board[r+1][c]=board[r+2][c]=-abs(board[r][c])\n",
    "                    crashed= True\n",
    "\n",
    "        for c in range(C):\n",
    "            write=R-1\n",
    "            for read in range(R-1,-1,-1):\n",
    "                if board[read][c]>0:\n",
    "                    board[write][c]= board[read][c]\n",
    "                    write-=1\n",
    "            for write in range(write,-1,-1):\n",
    "                board[write][c]=0\n",
    "        if crashed:\n",
    "            return self.candyCrush(board)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "\n",
    "        def bfs(i, j):\n",
    "            v = board[i][j]\n",
    "            visited = set()\n",
    "            # Test row\n",
    "            row_candies = []\n",
    "            x = i\n",
    "            while x < m and board[x][j] == v:\n",
    "                row_candies.append((x, j))\n",
    "                x += 1\n",
    "            if len(row_candies) >= 3:\n",
    "                visited.update(row_candies)\n",
    "            # Test column\n",
    "            column_candies = []\n",
    "            y = j\n",
    "            while y < n and board[i][y] == v:\n",
    "                column_candies.append((i, y))\n",
    "                y += 1\n",
    "            if len(column_candies) >= 3:\n",
    "                visited.update(column_candies)\n",
    "            return visited\n",
    "\n",
    "        while True:\n",
    "            # Judge what grids will be crushed\n",
    "            drop = [[0] * n for _ in range(m)]\n",
    "            should_drop = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    visited = bfs(i, j)\n",
    "                    if len(visited) >= 3:\n",
    "                        for x, y in visited:\n",
    "                            drop[x][y] = 1\n",
    "                            should_drop = True\n",
    "            if not should_drop:\n",
    "                return board\n",
    "\n",
    "            # Crush and drop each column\n",
    "            for j in range(n):\n",
    "                bottom = m - 1\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    if drop[i][j] == 1:\n",
    "                        continue\n",
    "                    board[bottom][j] = board[i][j]\n",
    "                    bottom -= 1\n",
    "                while bottom != -1:\n",
    "                    board[bottom][j] = 0\n",
    "                    bottom -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        found = True\n",
    "\n",
    "        while found:\n",
    "            crush = [[0] * n for _ in range(m)]\n",
    "\n",
    "            for i in range(m):\n",
    "                for j in range(n - 2):\n",
    "                    if board[i][j] == board[i][j + 1] == board[i][j + 2] != 0:\n",
    "                        crush[i][j], crush[i][j + 1], crush[i][j + 2] = 1, 1, 1\n",
    "            \n",
    "            for i in range(m - 2):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == board[i + 1][j] == board[i + 2][j] != 0:\n",
    "                        crush[i][j], crush[i + 1][j], crush[i + 2][j] = 1, 1, 1\n",
    "            \n",
    "            # Crush\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if crush[i][j]:\n",
    "                        board[i][j] = 0\n",
    "            \n",
    "            # Drop\n",
    "            for j in range(n):\n",
    "                idx = m - 1\n",
    "                for i in reversed(range(m)):\n",
    "                    if board[i][j]:\n",
    "                        board[idx][j] = board[i][j]\n",
    "                        idx -= 1\n",
    "                for i in range(idx + 1):\n",
    "                    board[i][j] = 0\n",
    "            \n",
    "            found = any(crush[i][j] for i in range(m) for j in range(n))\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            mark = set()\n",
    "            ok = False\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0: continue\n",
    "                    if j + 2 < n and board[i][j] == board[i][j+1] == board[i][j+2]:\n",
    "                        ok = True\n",
    "                        mark.add((i,j))\n",
    "                        mark.add((i,j + 1))\n",
    "                        mark.add((i, j+ 2))\n",
    "                    if i + 2 < m and board[i][j] == board[i+1][j] == board[i + 2][j]:\n",
    "                        ok = True\n",
    "                        mark.add((i,j))\n",
    "                        mark.add((i + 1,j))\n",
    "                        mark.add((i + 2,j))\n",
    "            if not ok: break\n",
    "            nb = [[0] * n for _ in range(m)]\n",
    "            for j in range(n):\n",
    "                k = m - 1\n",
    "                for i in range(m - 1, -1, -1):\n",
    "                    if (i, j) not in mark:\n",
    "                        nb[k][j] =  board[i][j]\n",
    "                        k -= 1\n",
    "            board = nb\n",
    "        return board\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\"\"\"\n",
    "思路：\n",
    "1. 创建一个形状一样的board，用来记录是否需要消除\n",
    "2. 两轮循环，通过判断左右三个 + 上下三个是否相等来判断是否需要消除，并进行标记\n",
    "3. 根据标记的矩阵进行消除并填补新的元素，方法为不断向上查找第一个不为0的元素，然后将其下移\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        def check_more2go(board, check):\n",
    "            flag = False\n",
    "            for i in range(1, m-1):\n",
    "                for j in range(0, n):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i-1][j] == board[i][j] == board[i+1][j]:\n",
    "                        check[i-1][j] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i+1][j] = True\n",
    "                        flag = True\n",
    "\n",
    "            for i in range(0, m):\n",
    "                for j in range(1, n-1):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i][j-1] == board[i][j] == board[i][j+1]:\n",
    "                        check[i][j-1] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i][j+1] = True\n",
    "                        flag = True\n",
    "            return flag\n",
    "\n",
    "        while True:\n",
    "            check = [[False] * n for _ in range(m)]\n",
    "            if not check_more2go(board, check):\n",
    "                return board\n",
    "            print(check)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if check[i][j]:\n",
    "                        board[i][j] = 0\n",
    "            print(board)\n",
    "            \n",
    "            # 模拟下坠\n",
    "            for i in range(m-1, -1, -1):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        for k in range(i-1, -1, -1):\n",
    "                            if board[k][j] != 0:\n",
    "                                board[i][j] = board[k][j]\n",
    "                                board[k][j] = 0\n",
    "                                break\n",
    "            print(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            vis = set()\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] != 0 and board[i][j] not in vis:\n",
    "                        v = board[i][j]\n",
    "                        x, y = j - 1, j + 1\n",
    "                        while x >= 0 and board[i][x] == v:\n",
    "                            x -= 1\n",
    "                        while y < n and board[i][y] == v:\n",
    "                            y += 1\n",
    "                        cnt = y - x - 1\n",
    "                        if cnt >= 3:\n",
    "                            for k in range(x + 1, y):\n",
    "                                vis.add((i, k))\n",
    "\n",
    "                        \n",
    "                        v = board[i][j]\n",
    "                        x, y = i - 1, i + 1\n",
    "                        while x >= 0 and board[x][j] == v:\n",
    "                            x -= 1\n",
    "                        while y < m and board[y][j] == v:\n",
    "                            y += 1\n",
    "                        cnt = y - x - 1\n",
    "                        if cnt >= 3:\n",
    "                            for k in range(x + 1, y):\n",
    "                                vis.add((k, j))\n",
    "            if len(vis) == 0: return board\n",
    "            for x, y in vis:\n",
    "                board[x][y] = 0  # 这里已经对网格里面的进行了更新\n",
    "            for j in range(n):   # 考虑每一列\n",
    "                a = []\n",
    "                for i in range(m - 1, -1, -1):  # 倒序遍历行，因为上面的要填到下面\n",
    "                    if board[i][j]:             # 如果有数值代表有糖果\n",
    "                        a.append(board[i][j])\n",
    "                    board[i][j] = 0             # 将这列的全部置0\n",
    "                k = len(a)                      # 这个代表这列一共有多少位置有糖果\n",
    "                for i in range(m - 1, m - k - 1, -1):  # 依然从倒序遍历，但填数字的上限在 m - k - 1，之后上面就都是没有糖果的了\n",
    "                    board[i][j] = a[m - i - 1]\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = set()\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.add((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.add((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            rem = []\n",
    "            # 水平\n",
    "            for i in range(m):\n",
    "                pre = board[i][0]\n",
    "                cnt = 1\n",
    "                for j in range(1, n):\n",
    "                    if pre == board[i][j]:\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        if cnt >= 3 and pre:\n",
    "                            rem.extend([i, k] for k in range(j - cnt, j))\n",
    "                        cnt = 1\n",
    "                        pre = board[i][j]\n",
    "                if cnt >= 3 and pre:\n",
    "                    rem.extend([i, k] for k in range(n - cnt, n))\n",
    "            # 竖直\n",
    "            for j in range(n):\n",
    "                pre = board[0][j]\n",
    "                cnt = 1\n",
    "                for i in range(1, m):\n",
    "                    if pre == board[i][j]:\n",
    "                        cnt += 1\n",
    "                    else:\n",
    "                        if cnt >= 3 and pre:\n",
    "                            rem.extend([k, j] for k in range(i - cnt, i))\n",
    "                        cnt = 1\n",
    "                        pre = board[i][j]\n",
    "                if cnt >= 3 and pre:\n",
    "                    rem.extend([k, j] for k in range(m - cnt, m))\n",
    "\n",
    "            if rem:\n",
    "                \n",
    "                flag = True\n",
    "                for i, j in rem:\n",
    "                    board[i][j] = 0\n",
    "                \n",
    "                # 移动值\n",
    "                for j in range(n):\n",
    "                    lst = []\n",
    "                    for i in range(m - 1, -1, -1):\n",
    "                        if board[i][j]:\n",
    "                            lst.append(board[i][j])\n",
    "                        board[i][j] = 0\n",
    "                    k = len(lst)\n",
    "                    for i in range(m - 1, m - k - 1, -1):\n",
    "                        board[i][j] = lst[m - 1 - i]\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        waitdelete = []\n",
    "        m, n = len(board), len(board[0])\n",
    "        def cancle(i,j):\n",
    "            curEle = board[i][j]\n",
    "            # go right\n",
    "            if curEle == 0:\n",
    "                return\n",
    "            if j < n-2:\n",
    "                idx = 0\n",
    "                while idx < n-j:\n",
    "                    if board[i][j+idx] == curEle:\n",
    "                        idx += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if idx >= 3:\n",
    "                    for i1 in range(idx):\n",
    "                        waitdelete.append((i,j+i1))\n",
    "            \n",
    "            # go down\n",
    "            if i < m-2:\n",
    "                jdx = 0\n",
    "                while jdx < m-i:\n",
    "                    if board[i+jdx][j] == curEle:\n",
    "                        jdx += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if jdx >= 3:\n",
    "                    for j1 in range(jdx):\n",
    "                        waitdelete.append((i+j1,j))\n",
    "        def runDown():\n",
    "            for i in range(m-1,-1,-1):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        zerolen = 0\n",
    "                        while i-zerolen>= 0 and board[i-zerolen][j] == 0:\n",
    "                            zerolen += 1\n",
    "                        for ss in range(i-zerolen+1):\n",
    "                            board[i-ss][j] = board[i-ss-zerolen][j]\n",
    "                        for ss in range(zerolen):\n",
    "                            board[ss][j] = 0\n",
    "            return \n",
    "\n",
    "\n",
    "\n",
    "        needRun = True\n",
    "        while needRun:\n",
    "            # print(\"==============\")\n",
    "            # for line in board:\n",
    "            #     print(line)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    cancle(i,j)\n",
    "            # print(waitdelete)\n",
    "            if len(waitdelete) == 0:\n",
    "                return board\n",
    "            for ele in waitdelete:\n",
    "                board[ele[0]][ele[1]] = 0\n",
    "            \n",
    "            waitdelete.clear()\n",
    "            runDown()\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\r\n",
    "        Row, Col = len(board), len(board[0])\r\n",
    "        need_todo = True\r\n",
    "        ################ 注意L形也是可以的\r\n",
    "        while need_todo:        #上一轮消消乐了，这一轮有可能还要继续消消乐\r\n",
    "            need_todo = False\r\n",
    "            #### 先搞定行\r\n",
    "            for r in range(Row):\r\n",
    "                for c in range(Col - 2):\r\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r][c+1]) == abs(board[r][c+2]):\r\n",
    "                        need_todo = True\r\n",
    "                        tmp = - abs(board[r][c])\r\n",
    "                        board[r][c]   = tmp\r\n",
    "                        board[r][c+1] = tmp\r\n",
    "                        board[r][c+2] = tmp\r\n",
    "            #### 再搞定列\r\n",
    "            for c in range(Col):\r\n",
    "                for r in range(Row - 2):\r\n",
    "                    if board[r][c] != 0 and abs(board[r][c]) == abs(board[r+1][c]) == abs(board[r+2][c]):\r\n",
    "                        need_todo = True\r\n",
    "                        tmp = -abs(board[r][c])\r\n",
    "                        board[r][c]   = tmp\r\n",
    "                        board[r+1][c] = tmp\r\n",
    "                        board[r+2][c] = tmp\r\n",
    "            #### 根据标记，整理。因为要从上往下掉落。要按列来\r\n",
    "            if need_todo == True:\r\n",
    "                for c in range(Col):\r\n",
    "                    rr = Row - 1\r\n",
    "                    for r in range(Row - 1, -1, -1):\r\n",
    "                        if board[r][c] > 0:\r\n",
    "                            board[rr][c] = board[r][c]\r\n",
    "                            rr -= 1\r\n",
    "                    while rr > -1:\r\n",
    "                        board[rr][c] = 0\r\n",
    "                        rr -= 1\r\n",
    "\r\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "\n",
    "        remove = [[False] * m for _ in range(n)]\n",
    "        todo = True\n",
    "        # first mark the elements to be eliminated horizontally\n",
    "        while todo:\n",
    "            todo = False\n",
    "            for r in range(n):\n",
    "                left = 0\n",
    "                right = 0\n",
    "                while left < m:\n",
    "                    while right < m and board[r][left] == board[r][right]:\n",
    "                        right += 1\n",
    "                    \n",
    "                    if right - left >= 3 and board[r][left] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(left, right):\n",
    "                            remove[r][idx] = True\n",
    "                    left = right\n",
    "    \n",
    "            # second mark the elements to be eliminated vertically\n",
    "            for c in range(m):\n",
    "                up = 0\n",
    "                down = 0\n",
    "                while up < n:\n",
    "                    while down < n and board[up][c] == board[down][c]:\n",
    "                        down += 1\n",
    "                    \n",
    "                    if down - up >= 3 and board[up][c] != 0:\n",
    "                        todo = True\n",
    "                        for idx in range(up, down):\n",
    "                            remove[idx][c] = True\n",
    "                    up = down\n",
    "            \n",
    "            # vertically squash every removed element row by row from bottom to top\n",
    "            for r in range(n - 1, -1, -1):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        index = r\n",
    "                        while index >= 0 and remove[index][c]:\n",
    "                            index -= 1\n",
    "                        if index >= 0:\n",
    "                            board[r][c] = board[index][c]\n",
    "                            remove[r][c] = False\n",
    "                            remove[index][c] = True\n",
    "            \n",
    "            for r in range(n):\n",
    "                for c in range(m):\n",
    "                    if remove[r][c]:\n",
    "                        board[r][c] = 0\n",
    "        return board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def crush():\n",
    "            to_crush = set()\n",
    "            for i in range(m):\n",
    "                j1 = 0\n",
    "                for j2 in range(n + 1):\n",
    "                    if j2 == n or board[i][j2] != board[i][j1]:\n",
    "                        if j2 - j1 >= 3 and board[i][j1]:\n",
    "                            for k in range(j1, j2):\n",
    "                                to_crush.add((i, k))\n",
    "                        j1 = j2\n",
    "            for j in range(n):\n",
    "                i1 = 0\n",
    "                for i2 in range(m + 1):\n",
    "                    if i2 == m or board[i2][j] != board[i1][j]:\n",
    "                        if i2 - i1 >= 3 and board[i1][j]:\n",
    "                            for k in range(i1, i2):\n",
    "                                to_crush.add((k, j))\n",
    "                        i1 = i2\n",
    "            for i, j in to_crush:\n",
    "                board[i][j] = 0\n",
    "            return len(to_crush)\n",
    "\n",
    "        def drop():\n",
    "            for j in range(n):\n",
    "                i1 = m - 1\n",
    "                for i2 in range(m-1, -1, -1):\n",
    "                    if board[i2][j]:\n",
    "                        board[i1][j] = board[i2][j]\n",
    "                        i1 -= 1\n",
    "                while i1 >= 0:\n",
    "                    board[i1][j] = 0\n",
    "                    i1 -= 1\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        while crush() > 0:\n",
    "            drop()\n",
    "        return board\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\"\"\"\n",
    "思路：\n",
    "1. 创建一个形状一样的board，用来记录是否需要消除\n",
    "2. 两轮循环，通过判断左右三个 + 上下三个是否相等来判断是否需要消除，并进行标记\n",
    "3. 根据标记的矩阵进行消除并填补新的元素，方法为不断向上查找第一个不为0的元素，然后将其下移\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        def check_more2go(board, check):\n",
    "            flag = False\n",
    "            for i in range(1, m-1):\n",
    "                for j in range(0, n):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i-1][j] == board[i][j] == board[i+1][j]:\n",
    "                        check[i-1][j] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i+1][j] = True\n",
    "                        flag = True\n",
    "\n",
    "            for i in range(0, m):\n",
    "                for j in range(1, n-1):\n",
    "                    # 记得考虑board[i][j]为0的情况\n",
    "                    if board[i][j] == 0:\n",
    "                        continue\n",
    "                    if board[i][j-1] == board[i][j] == board[i][j+1]:\n",
    "                        check[i][j-1] = True\n",
    "                        check[i][j] = True\n",
    "                        check[i][j+1] = True\n",
    "                        flag = True\n",
    "            return flag\n",
    "\n",
    "        while True:\n",
    "            check = [[False] * n for _ in range(m)]\n",
    "            if not check_more2go(board, check):\n",
    "                return board\n",
    "            print(check)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if check[i][j]:\n",
    "                        board[i][j] = 0\n",
    "            print(board)\n",
    "            \n",
    "            # 模拟下坠\n",
    "            # 必须从最后一行开始\n",
    "            for i in range(m-1, -1, -1):\n",
    "                for j in range(n):\n",
    "                    if board[i][j] == 0:\n",
    "                        for k in range(i-1, -1, -1):\n",
    "                            if board[k][j] != 0:\n",
    "                                board[i][j] = board[k][j]\n",
    "                                board[k][j] = 0\n",
    "                                break\n",
    "            print(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        def check():\n",
    "            state = [[0] * n for _ in range(m)]\n",
    "            signal = 0\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n - 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur != 0 and cur == board[i][j + 1] and cur == board[i][j + 2]:\n",
    "                        signal = 1\n",
    "                        state[i][j:j+3] = [1]*3\n",
    "                        j += 2\n",
    "                        while j + 1 < n and board[i][j + 1] == board[i][j]:\n",
    "                            state[i][j + 1] = 1\n",
    "                            j += 1\n",
    "                    j += 1\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                while i >= 2:\n",
    "                    cur = board[i][j]\n",
    "                    if cur == 0:\n",
    "                        break\n",
    "                    if cur == board[i - 1][j] and cur == board[i - 2][j]:\n",
    "                        signal = 1\n",
    "                        for x in range(i, i - 3, -1):\n",
    "                            state[x][j] = 1\n",
    "                        i -= 2\n",
    "                        while i >= 1 and board[i - 1][j] == board[i][j]:\n",
    "                            state[i - 1][j] = 1\n",
    "                            i -= 1\n",
    "                    i -= 1\n",
    "            return state, signal\n",
    "        \n",
    "        def revise(state):\n",
    "            for j in range(n):\n",
    "                i = m - 1\n",
    "                pos = m - 1\n",
    "                while pos >= 0:\n",
    "                    if state[pos][j] != 1:\n",
    "                        board[i][j] = board[pos][j]\n",
    "                        i -= 1\n",
    "                    pos -= 1\n",
    "                while i >= 0:\n",
    "                    board[i][j] = 0\n",
    "                    i -= 1\n",
    "        \n",
    "        m, n = len(board), len(board[0])\n",
    "        while True:\n",
    "            sta, sig = check()\n",
    "            if sig == 0:\n",
    "                return board\n",
    "            revise(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(board), len(board[0])\n",
    "        boom = [[False]*n for _ in range(m)]\n",
    "\n",
    "        def update():\n",
    "            stable = True\n",
    "\n",
    "            # 获取待粉碎的糖果\n",
    "            for i in range(m):\n",
    "                j = 0\n",
    "                while j < n:\n",
    "                    if board[i][j] == 0:\n",
    "                        j += 1\n",
    "                        continue\n",
    "                    k = j + 1\n",
    "                    while k < n and board[i][k] == board[i][j]:\n",
    "                        k += 1\n",
    "                    if k - j >= 3:\n",
    "                        stable = False\n",
    "                        for jj in range(j, k):\n",
    "                            boom[i][jj] = True\n",
    "                    j = k\n",
    "            for j in range(n):\n",
    "                i = 0\n",
    "                while i < m:\n",
    "                    if board[i][j] == 0:\n",
    "                        i += 1\n",
    "                        continue\n",
    "                    k = i + 1\n",
    "                    while k < m and board[k][j] == board[i][j]:\n",
    "                        k += 1\n",
    "                    if k - i >= 3:\n",
    "                        stable = False\n",
    "                        for ii in range(i, k):\n",
    "                            boom[ii][j] = True\n",
    "                    i = k\n",
    "            \n",
    "            if stable:\n",
    "                return\n",
    "\n",
    "            # 更新\n",
    "            for j in range(n):\n",
    "                i0 = i1 = m - 1\n",
    "                while i1 >= 0:\n",
    "                    if boom[i1][j]:\n",
    "                        i1 -= 1\n",
    "                        continue\n",
    "                    board[i0][j] = board[i1][j]\n",
    "                    i0 -= 1\n",
    "                    i1 -= 1\n",
    "                for i1 in range(i0, -1, -1):\n",
    "                    board[i1][j] = 0\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    boom[i][j] = False\n",
    "            update()\n",
    "        \n",
    "        update()\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param board:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "\n",
    "        def detect_to_remove(b1):\n",
    "            rmidx = set()\n",
    "            for k,v in enumerate(b1):\n",
    "                for k2,v2 in enumerate(v):\n",
    "                    if v2 == 0:\n",
    "                        continue\n",
    "                    dq1 = deque()\n",
    "                    dq1.append((k,k2))\n",
    "                    used = set()\n",
    "                    while dq1:\n",
    "                        idx1 = dq1.popleft()\n",
    "                        dict1 = [(0,1), (0, -1)]\n",
    "                        if idx1 in used:\n",
    "                            continue\n",
    "                        used.add(idx1)\n",
    "                        for i in dict1:\n",
    "                            newidx = idx1[0] + i[0], idx1[1] + i[1]\n",
    "                            if 0 <= newidx[0] < len(b1) and 0 <= newidx[1] < len(b1[0]) and b1[newidx[0]][newidx[1]] == v2:\n",
    "                                dq1.append(newidx)\n",
    "                    if len(used) >= 3:\n",
    "                        for i in used:\n",
    "                            rmidx.add(i)\n",
    "\n",
    "                    dq1 = deque()\n",
    "                    dq1.append((k, k2))\n",
    "                    used = set()\n",
    "                    while dq1:\n",
    "                        idx1 = dq1.popleft()\n",
    "                        dict1 = [(1, 0), (-1, 0)]\n",
    "                        if idx1 in used:\n",
    "                            continue\n",
    "                        used.add(idx1)\n",
    "                        for i in dict1:\n",
    "                            newidx = idx1[0] + i[0], idx1[1] + i[1]\n",
    "                            if 0 <= newidx[0] < len(b1) and 0 <= newidx[1] < len(b1[0]) and b1[newidx[0]][\n",
    "                                newidx[1]] == v2:\n",
    "                                dq1.append(newidx)\n",
    "                    if len(used) >= 3:\n",
    "                        for i in used:\n",
    "                            rmidx.add(i)\n",
    "\n",
    "            return rmidx\n",
    "\n",
    "\n",
    "        def adjust_board(id_list, b1):\n",
    "            for i in id_list:\n",
    "                b1[i[0]][i[1]] = 0\n",
    "            new_m = []\n",
    "            for i in range(len(b1[0])):\n",
    "                newl = []\n",
    "                for j in range(len(b1)):\n",
    "                    if b1[j][i] != 0:\n",
    "                        newl.append(b1[j][i])\n",
    "                while len(newl) < len(b1):\n",
    "                    newl.insert(0, 0)\n",
    "                new_m.append(newl)\n",
    "            for i in range(len(new_m)):\n",
    "                for j in range(len(new_m[0])):\n",
    "                    b1[j][i] = new_m[i][j]\n",
    "\n",
    "\n",
    "        def get_cmp(cur, ll):\n",
    "            idx = 0\n",
    "            for i in ll:\n",
    "                if i > cur:\n",
    "                    idx += 1\n",
    "            return idx\n",
    "\n",
    "        while True:\n",
    "            v1 = detect_to_remove(board)\n",
    "            if len(v1) == 0:\n",
    "                break\n",
    "            adjust_board(v1, board)\n",
    "        return board\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        if not ratings:\n",
    "            return 0\n",
    "\n",
    "        _len = len(ratings)\n",
    "        ans = _len * [1]\n",
    "        for i in range(1, _len):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                ans[i] = ans[i - 1] + 1\n",
    "\n",
    "        for i in range(1, _len):\n",
    "            if ratings[_len - i] < ratings[_len - 1 - i]:\n",
    "                ans[_len - i - 1] = max(ans[_len - i] + 1, ans[_len - 1 - i])\n",
    "\n",
    "        return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        children = len(ratings)\n",
    "        res = [1 for _ in range(children)]\n",
    "        for i in range(1, children):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                res[i] = res[i-1]+1\n",
    "        for i in range(children-2, -1, -1):\n",
    "            if ratings[i] > ratings[i+1] and res[i] <= res[i+1]:\n",
    "                res[i] = res[i+1]+1\n",
    "        # print(res)\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(ratings)\n",
    "        arr = ratings\n",
    "        cache = [1]*n\n",
    "        for i in range(1, n):\n",
    "            if arr[i] > arr[i-1]:\n",
    "                cache[i] = cache[i-1] + 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if arr[i] > arr[i+1] and cache[i] <= cache[i+1]:\n",
    "                cache[i] = cache[i+1] + 1   \n",
    "        return sum(cache)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(ratings)\n",
    "        c = [1]*n\n",
    "        for i in range(1,n):\n",
    "            if ratings[i]>ratings[i-1]:\n",
    "                c[i] = c[i-1]+1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if ratings[i]>ratings[i+1]:\n",
    "                c[i] = max(c[i],c[i+1]+1)\n",
    "        s = sum(c)\n",
    "        return s\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        if not ratings:\n",
    "            return 0\n",
    "        nums = [1]\n",
    "        cnt = 1\n",
    "        for i in range(1,len(ratings)):\n",
    "            if ratings[i]>ratings[i-1]:\n",
    "                cnt += 1 \n",
    "            else:\n",
    "                cnt=1\n",
    "            nums.append(cnt)\n",
    "        cnt = nums[-1]\n",
    "        for j in range(len(ratings)-2,-1,-1):\n",
    "            if ratings[j]>ratings[j+1]:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                cnt = 1\n",
    "            nums[j] = max(nums[j],cnt)\n",
    "        return sum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        if ratings == []:\n",
    "            return 0\n",
    "        # 先给每个小孩分一个糖果，确保没人会遗漏\n",
    "        result = [1]*len(ratings)\n",
    "\n",
    "        for i in range(1,len(ratings)):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                result[i] = result[i-1]+1\n",
    "\n",
    "        for j in range(len(ratings)-2,-1,-1):\n",
    "            if ratings[j] > ratings[j+1] and result[j] <= result[j+1]:\n",
    "                result[j] = result[j+1]+1\n",
    "\n",
    "        return sum(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        rat_len = len(ratings)\n",
    "        res = [1]*rat_len\n",
    "        for i in range(1, rat_len):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                res[i] = res[i-1] + 1\n",
    "                \n",
    "        for i in range(rat_len-1, 0, -1):\n",
    "            if ratings[i-1] > ratings[i] and res[i-1] <= res[i]:\n",
    "                res[i-1] = res[i] + 1\n",
    "              \n",
    "        print(res)\n",
    "        return sum(res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#coding=gbk\n",
    "class Solution:\n",
    "\tdef candy(self, ratings):\n",
    "\t\tratings.append(ratings[-1])\n",
    "\t\tpeaks=[]\n",
    "\t\t#用count来计算重复的数量\n",
    "\t\tcount=0\n",
    "\t\tmountain=[ratings[0]]\n",
    "\t\tpp=False\n",
    "\t\tfor i in range(1,len(ratings)):\n",
    "\t\t\t#当出现两者相等时,直接截断\n",
    "\t\t\tif ratings[i]==mountain[-1]:\n",
    "\t\t\t\tpeaks.append(mountain)\n",
    "\t\t\t\tmountain=[ratings[i]]\n",
    "\t\t\t\tpp=False\n",
    "\t\t\telif not pp:\n",
    "\t\t\t\tif ratings[i]>mountain[-1]:\n",
    "\t\t\t\t\tmountain.append(ratings[i])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tpp=True\n",
    "\t\t\t\t\tmountain.append(ratings[i])\n",
    "\t\t\telse:\n",
    "\t\t\t\tif ratings[i]>mountain[-1]:\n",
    "\t\t\t\t\tpeaks.append(mountain)\n",
    "\t\t\t\t\tmountain=[mountain[-1],ratings[i]]\n",
    "\t\t\t\t\tcount+=1\n",
    "\t\t\t\t\tpp=False\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tmountain.append(ratings[i])\n",
    "\t\tre=0\n",
    "\t\tprint(peaks)\n",
    "\t\tfor peak in peaks:\n",
    "\t\t\tl=len(peak)\n",
    "\t\t\tindex=peak.index(max(peak))+1\n",
    "\t\t\tmax1=max(l-index,index-1)+1\n",
    "\t\t\tre+=max1+(l-index)*(l-index+1)//2+(index-1)*index//2\n",
    "\t\treturn re-count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(ratings)\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        attr = []\n",
    "        pre = 1\n",
    "        for i in range(n):\n",
    "            if i < n-1:\n",
    "                if ratings[i] < ratings[i+1]:\n",
    "                    cur = 0\n",
    "                elif ratings[i] == ratings[i+1]:\n",
    "                    cur = 1\n",
    "                else:\n",
    "                    cur = 2\n",
    "            else:\n",
    "                cur = 1\n",
    "            if pre >= 1 and cur == 0 or pre==2 and cur<=1:\n",
    "                attr.append((i,0))\n",
    "            elif pre == 1 and cur == 1:\n",
    "                attr.append((i,1))\n",
    "            elif pre <= 1 and cur == 2 or pre==0 and cur >= 1:\n",
    "                attr.append((i,2))\n",
    "            pre = cur\n",
    "        total = 0\n",
    "        pre = 1\n",
    "        n_attr = len(attr)\n",
    "        repeat = 0\n",
    "        end = -1\n",
    "        for i in range(0,n_attr):\n",
    "            loc, cur = attr[i]\n",
    "            if cur == 2:\n",
    "                if i == 0:\n",
    "                    d1 = attr[i + 1][0] - attr[i][0] + 1\n",
    "                    d2 = 1\n",
    "                    end = attr[i+1][0]\n",
    "                    repeat = 0\n",
    "                elif i == n_attr - 1:\n",
    "                    d1 = attr[i][0] - attr[i - 1][0] + 1\n",
    "                    d2 = 1\n",
    "                    if end == attr[i - 1][0]:\n",
    "                        repeat = 1\n",
    "                    else:\n",
    "                        repeat = 0\n",
    "                else:\n",
    "                    d1 = attr[i][0] - attr[i - 1][0] + 1\n",
    "                    d2 = attr[i + 1][0] - attr[i][0] + 1\n",
    "                    if attr[i-1][1]== 0 and attr[i+1][1]== 0 and ratings[attr[i-1][0]] != ratings[attr[i][0]] and  ratings[attr[i][0]] != ratings[attr[i+1][0]]:\n",
    "                        if d1<d2:\n",
    "                            d1,d2 = d2,d1\n",
    "                        if end == attr[i - 1][0]:\n",
    "                            repeat = 1\n",
    "                        else:\n",
    "                            repeat = 0\n",
    "                        end = attr[i+1][0]\n",
    "                    elif attr[i-1][1] == 0 and ratings[attr[i-1][0]] != ratings[attr[i][0]]:\n",
    "                        d2 = 1\n",
    "                        if end == attr[i - 1][0]:\n",
    "                            repeat = 1\n",
    "                        else:\n",
    "                            repeat = 0\n",
    "                        end = attr[i][0]\n",
    "                    else:\n",
    "                        d1 = d2\n",
    "                        d2 = 1\n",
    "                        end = attr[i + 1][0]\n",
    "                        repeat = 0\n",
    "                total += (d1 + 1) * d1 // 2 + (d2 - 1) * d2 // 2 - repeat\n",
    "            elif cur == 1:\n",
    "                total += 1\n",
    "        return total\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        num_children = len(ratings)\n",
    "        if num_children == 0 or num_children == 1:\n",
    "            return num_children\n",
    "        \n",
    "        bigger = [0] * num_children\n",
    "        smaller = [0] * num_children\n",
    "        \n",
    "        bigger_count = 0\n",
    "        for i in range(1, num_children):\n",
    "            if ratings[i] > ratings[i - 1]:\n",
    "                bigger_count += 1\n",
    "            else:\n",
    "                bigger_count = 0\n",
    "            bigger[i] = bigger_count\n",
    "            \n",
    "        smaller_count = 0\n",
    "        for i in range(num_children-2, -1, -1):\n",
    "            if ratings[i] > ratings[i + 1]:\n",
    "                smaller_count += 1\n",
    "            else:\n",
    "                smaller_count = 0\n",
    "            smaller[i] = smaller_count\n",
    "            \n",
    "        \n",
    "        nums = [max(b,s)+1 for b,s in zip(bigger, smaller)]\n",
    "                \n",
    "                \n",
    "                \n",
    "        return sum(nums)\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left2right = [1]\n",
    "        right2left = [1]\n",
    "        for i in range(1, len(ratings)):\n",
    "            l2r = i\n",
    "            r2l = len(ratings) - 1 - i\n",
    "            \n",
    "            if ratings[l2r] > ratings[l2r - 1]:\n",
    "                left2right.append(left2right[-1] + 1)\n",
    "            else:\n",
    "                left2right.append(1)\n",
    "            \n",
    "            if ratings[r2l + 1] < ratings[r2l]:\n",
    "                right2left.insert(0, right2left[0] + 1)\n",
    "            else:\n",
    "                right2left.insert(0, 1)\n",
    "                \n",
    "        candy = 0\n",
    "        for i in range(len(ratings)):\n",
    "            candy += max(left2right[i], right2left[i])\n",
    "        \n",
    "        print(left2right, right2left)\n",
    "        \n",
    "        return candy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings):\n",
    "        \"\"\"\n",
    "        :type ratings: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        test = ''\n",
    "        for ind in range(len(ratings)-1):\n",
    "            if ratings[ind] < ratings[ind+1]: # 只有這三種可能\n",
    "                test += 'a' # add (+)\n",
    "            elif ratings[ind] > ratings[ind+1]:\n",
    "                test += 's' # subtract (-)\n",
    "            else: # ratings[ind] == ratings[ind+1]:\n",
    "                test += 'e' # equal (=)\n",
    "        lst = []\n",
    "        for s in test.split('e'):\n",
    "            if not s:\n",
    "                lst.append(1)\n",
    "            else:\n",
    "                l = [1]\n",
    "                for x in s:\n",
    "                    if x == 'a':\n",
    "                        l.append(l[-1]+1)\n",
    "                    else:\n",
    "                        l.append(l[-1]-1)\n",
    "                if min(l) == 1:\n",
    "                    pass\n",
    "                else:\n",
    "                    d = min(l) - 1\n",
    "                    ind = 0\n",
    "                    while ind != len(l):\n",
    "                        l[ind] -= d\n",
    "                        ind += 1\n",
    "                while True:\n",
    "                    arr = l.copy()\n",
    "                    if l[0] < l[1]:\n",
    "                        l[0] = 1\n",
    "                    if l[0] > l[1]:\n",
    "                        l[0] = l[1] + 1\n",
    "                    if l[-2] > l[-1]:\n",
    "                        l[-1] = 1\n",
    "                    if l[-2] < l[-1]:\n",
    "                        l[-1] = l[-2] + 1 \n",
    "                    for ind in range(1, len(l)-1):\n",
    "                        if l[ind] > l[ind-1] and l[ind] > l[ind+1]:\n",
    "                            l[ind] = (max([l[ind+1], l[ind-1]]) + 1)\n",
    "                        elif l[ind] < l[ind-1] and l[ind] < l[ind+1]:\n",
    "                            l[ind] = 1\n",
    "                        else:\n",
    "                            l[ind] = (min([l[ind+1], l[ind-1]]) + 1)\n",
    "                    if arr == l:\n",
    "                        break\n",
    "                lst.extend(l)\n",
    "        return sum(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        if not ratings:\n",
    "            return 0\n",
    "        ratings.append(float(\"inf\"))\n",
    "        state=1\n",
    "        start=end=0\n",
    "        result=1\n",
    "        last=1\n",
    "        for i in range(1,len(ratings)):\n",
    "            if ratings[i]>=ratings[i-1]:\n",
    "                if state==-1:\n",
    "                    if start !=end:\n",
    "                        if end-start+1>last:\n",
    "                            result-=last\n",
    "                            result+=end-start+1\n",
    "                        result+=(end-start+1)*(end-start)/2\n",
    "                        last=1\n",
    "                if ratings[i]>ratings[i-1]:\n",
    "                    result+=last+1\n",
    "                    last+=1\n",
    "                else:\n",
    "                    result+=1\n",
    "                    last=1\n",
    "                start=end=i\n",
    "                state=1\n",
    "            else:\n",
    "                end=i\n",
    "                state=-1\n",
    "            #print(i,result,(start,end))\n",
    "        return int(result-last)\n",
    "                \n",
    "            \n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        length=len(ratings)\n",
    "        if length==0:\n",
    "            return 0\n",
    "        candy=[1]*length\n",
    "        for i in range(1,length):\n",
    "            if ratings[i]>ratings[i-1]:\n",
    "                candy[i]=candy[i-1]+1\n",
    "        for i in range(length-1,0,-1):\n",
    "            if ratings[i-1]>ratings[i] and candy[i-1]<=candy[i]:\n",
    "                candy[i-1]=candy[i]+1\n",
    "        #print(candy)\n",
    "        return sum(candy)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        # length = len(ratings)\n",
    "        # res = [[1 for _ in range(length)] for _ in range(2)]\n",
    "        # for i in range(1, length):\n",
    "        #     if ratings[i] > ratings[i - 1]:\n",
    "        #         res[0][i] = res[0][i - 1] + 1\n",
    "        #     if ratings[length - i - 1] > ratings[length - i]:\n",
    "        #         res[1][length - i - 1] = res[1][length - i] + 1\n",
    "        # out = []\n",
    "        # for i in range(length):\n",
    "        #     out.append(max(res[0][i], res[1][i]))\n",
    "        # print(res)\n",
    "        # return sum(out)\n",
    "\n",
    "        res = 1\n",
    "        # 先前值\n",
    "        pre = 1\n",
    "        # 递减长度\n",
    "        des_num = 0\n",
    "        for i in range(1, len(ratings)):\n",
    "            if ratings[i] >= ratings[i - 1]:\n",
    "                if des_num > 0:\n",
    "                    # 求和公式\n",
    "                    res += ((1 + des_num) * des_num) // 2\n",
    "                    # 递减长度比先前值大,所以我们要把先前值补充\n",
    "                    if pre <= des_num: res += (des_num - pre + 1)\n",
    "                    pre = 1\n",
    "                    des_num = 0\n",
    "                if ratings[i] == ratings[i - 1]:\n",
    "                    pre = 1\n",
    "                else:\n",
    "                    pre += 1\n",
    "                res += pre\n",
    "            else:\n",
    "                des_num += 1\n",
    "        # print(des_num)\n",
    "        if des_num > 0:\n",
    "            res += ((1 + des_num) * des_num) // 2\n",
    "            if pre <= des_num: res += (des_num - pre + 1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        candies = [1 for i in  range(len(ratings))]\n",
    "        for i in range(1, len(ratings)):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                candies[i] = candies[i-1] + 1\n",
    "        for i in range(len(ratings)-2,-1,-1):\n",
    "            if ratings[i] > ratings[i+1]:\n",
    "                candies[i] = max(candies[i], candies[i+1] + 1)\n",
    "        return sum(candies)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        # 分别记录连续减和连续增，需要额外分糖果\n",
    "        for i in range(1, n):\n",
    "            if ratings[i] < ratings[i-1]:\n",
    "                left[i] = left[i-1] + 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if ratings[i] < ratings[i+1]:\n",
    "                right[i] = right[i+1] + 1\n",
    "        res = n + sum(left) + sum(right)\n",
    "        # 对于峰顶位置，由于左右侧重复计算，需要额外处理，减去小的数\n",
    "        pos = []\n",
    "        for i in range(1, n-1):\n",
    "            if left[i] == 0 and right[i] == 0:\n",
    "                pos.append(i)\n",
    "        for num in pos:\n",
    "            l, r = num+1, num-1\n",
    "            while l < n and left[l] > left[l-1]:\n",
    "                l += 1\n",
    "            while r >= 0 and right[r] > right[r+1]:\n",
    "                r -= 1\n",
    "            res -= min(left[l-1], right[r+1])\n",
    "        return res         \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        if len(ratings)==1:return 1\n",
    "        if not ratings:return 0\n",
    "        candy=[0 for i in range(len(ratings))]\n",
    "        if ratings[0]<=ratings[1]:\n",
    "            candy[0]=1\n",
    "            cur=1\n",
    "            while cur<=len(ratings)-1 and ratings[cur-1]<ratings[cur]:\n",
    "                candy[cur]=1+candy[cur-1]\n",
    "                cur+=1\n",
    "        for i in range(1,len(ratings)-1):\n",
    "            if ratings[i-1]>=ratings[i]<=ratings[i+1]:\n",
    "                candy[i]=1\n",
    "                l,r=i-1,i+1\n",
    "                while l>=0 and ratings[l]>ratings[l+1]:\n",
    "                    candy[l]=max(candy[l],1+candy[l+1])\n",
    "                    l-=1\n",
    "                while r<=len(ratings)-1 and ratings[r]>ratings[r-1]:\n",
    "                    candy[r]=1+candy[r-1]\n",
    "                    r+=1\n",
    "        if ratings[-1]<=ratings[-2]:\n",
    "            candy[-1]=1\n",
    "            cur=len(ratings)-2\n",
    "            while cur>=0 and ratings[cur]>ratings[cur+1]:\n",
    "                candy[cur]=max(candy[cur],1+candy[cur+1])\n",
    "                cur-=1\n",
    "\n",
    "        return sum(candy)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "        left = [1 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                left[i] = left[i-1] + 1\n",
    "        right = [1 for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if ratings[i] > ratings[i+1]:\n",
    "                right[i] = right[i+1] + 1\n",
    "        \n",
    "        res = sum([max(i, j) for i, j in zip(left, right)])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "        left = [1 for _ in range(n)]\n",
    "        right = left[:]\n",
    "        for i in range(1, n):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                left[i] = left[i-1] + 1\n",
    "        res = left[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if ratings[i] > ratings[i+1]:\n",
    "                right[i] = right[i+1] + 1\n",
    "            res += max(left[i], right[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        total = [0]*(len(ratings)+1)\n",
    "        ratings.append(-float('inf'))\n",
    "        for i in sorted(range(len(ratings)-1), key = ratings.__getitem__):\n",
    "            total[i] = max(total[i-1]+1 if ratings[i-1]<ratings[i] else 1, total[i+1]+1 if ratings[i+1]<ratings[i] else 1)\n",
    "        return sum(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, rating: List[int]) -> int:\n",
    "        left,right,ans = [1]*len(rating),[1]*len(rating),0\n",
    "        for i in range(1,len(rating)):\n",
    "            if rating[i]>rating[i-1]:\n",
    "                left[i] = left[i-1]+1\n",
    "        for j in range(len(rating)-1,0,-1):\n",
    "            if rating[j]<rating[j-1]:\n",
    "                right[j-1]=right[j]+1\n",
    "            ans+=max(left[j],right[j])\n",
    "            \n",
    "        return ans+right[0]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        candy=[1]*len(ratings)\n",
    "        for i in range(1,len(ratings)):\n",
    "            if ratings[i]>ratings[i-1]:\n",
    "                candy[i]=candy[i-1]+1\n",
    "        for i in range(len(ratings)-2,-1,-1):\n",
    "            if ratings[i]>ratings[i+1]:\n",
    "                candy[i]=max(candy[i],candy[i+1]+1)\n",
    "        return sum(candy)\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        l = len(ratings)\n",
    "        res = [1] * l\n",
    "        for i in range(l - 1):\n",
    "            if ratings[i + 1] > ratings[i]:\n",
    "                res[i + 1] = res[i] + 1\n",
    "        for i in range(l - 1, 0, -1):\n",
    "            if ratings[i - 1] > ratings[i]:\n",
    "                res[i - 1] = max(res[i] + 1, res[i - 1])\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "\n",
    "        candys = [1]*n\n",
    "        for i in range(1, n):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                candys[i] = candys[i-1]+1\n",
    "        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            if ratings[i] > ratings[i+1] and candys[i] <= candys[i+1]:\n",
    "                candys[i] = candys[i+1]+1\n",
    "\n",
    "        return sum(candys)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "\n",
    "        candys = [1]*n\n",
    "        for i in range(1, n):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                candys[i] = candys[i-1]+1\n",
    "        \n",
    "        for i in range(n-2, -1, -1):\n",
    "            if ratings[i] > ratings[i+1] and candys[i] <= candys[i+1]:\n",
    "                candys[i] = candys[i+1]+1\n",
    "\n",
    "        return sum(candys)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "        s = [1]*n\n",
    "        r = [1]*n\n",
    "        for i in range(1,n):\n",
    "            if ratings[i]>ratings[i-1]:\n",
    "                s[i]=s[i-1]+1\n",
    "\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            if ratings[i]>ratings[i+1]:\n",
    "                r[i]=r[i+1]+1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += max(s[i],r[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int])-> int:\n",
    "        n = len(ratings)\n",
    "        left = [0] * n\n",
    "        for i in range(n):\n",
    "            if i > 0 and ratings[i] > ratings[i - 1]:\n",
    "                left[i] = left[i - 1] + 1\n",
    "            else:\n",
    "                left[i] = 1\n",
    "        right = ret = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i < n - 1 and ratings[i] > ratings[i + 1]:\n",
    "                right += 1\n",
    "            else:\n",
    "                right = 1\n",
    "            ret += max(left[i], right)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        N = len(ratings)\n",
    "        candies = [1] * N \n",
    "        for i in range(1,N):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                candies[i] = candies[i-1] + 1\n",
    "        for i in range(N-2,-1,-1):\n",
    "            if ratings[i] > ratings[i+1]:\n",
    "                candies[i] = max(candies[i],candies[i+1] + 1)\n",
    "        total = 0 \n",
    "        for c in candies:\n",
    "            total += c\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        n = len(ratings)\n",
    "        result = [1] * n\n",
    "        for i in range(1,n):\n",
    "            if ratings[i] > ratings[i-1]:\n",
    "                result[i] = result[i-1] + 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if ratings[i] > ratings[i+1] and result[i] <= result[i+1] :\n",
    "                result[i] = result[i+1] + 1\n",
    "        sum_result = 0\n",
    "        for i in range(n):\n",
    "            sum_result += result[i]\n",
    "        return sum_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        size=len(ratings)\n",
    "        num=[]\n",
    "        for i in range(size):\n",
    "            num.append(1)\n",
    "        if size<2:\n",
    "            return size\n",
    "        for i in range(1,size):\n",
    "            if(ratings[i]>ratings[i-1]):\n",
    "                num[i]=num[i-1]+1\n",
    "        for i in range(size-1,0,-1):\n",
    "            if(ratings[i-1]>ratings[i]):\n",
    "                num[i-1]=max(num[i-1],num[i]+1)\n",
    "        return sum(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def candy(self, ratings: List[int]) -> int:\n",
    "        left, right = [1 for _ in range(len(ratings))], [1 for _ in range(len(ratings))]\n",
    "        for i in range(1, len(ratings)):\n",
    "            if ratings[i]>ratings[i-1]:\n",
    "                left[i] = left[i-1] + 1\n",
    "        res = left[-1]\n",
    "        for i in range(len(ratings)-2, -1, -1):\n",
    "            if ratings[i]>ratings[i+1]:\n",
    "                right[i] = right[i+1] + 1\n",
    "            res += max(right[i], left[i])\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
